Garbage collectors free the space held by unreachable (dead) objects so that this space can be reused in future allocations.
An on-the-fly garbage collector, i.e., a collector that reclaims unused space in parallel to the running program without stopping it for the collection is a fascinating theoretical idea with important benefits in practice. In particular, in many server platforms the actual operation of stopping all parallel threads in order to do a garbage collection task is a high cost time consuming operation. The reason is that the threads cannot be stopped at any point and thus there is a relatively long wait until the last (of many) threads reaches a point where it may stop.
The study of on-the-fly garbage collectors was initiated by Steeles and Dijkstra et. al. [14, 15, 4] and was continued in a series of many papers (see for example [5,8,1,2,11 and 12] culminating in the Doligez-Gonthier-Leroy (DGL) collector [6,7].
The specified collectors are of the so called mark and sweep collector type. In these type of collectors, there is normally a first step, in which the live objects in the heap are marked and there is a second step in which the unmarked objects are "swept", i.e., reclaimed for future use.
The trace of live objects is done with a 3-color scheme: Objects are white if they have not been traced, they are marked gray if they have been traced but their immediate children have not been traced yet, and they are marked black if they have been traced and their immediate children have been traced as well. The trace proceeds step by step by taking a gray object, marking it black and marking gray all its white children.
The fact that the collector works "on-the-fly" makes its life harder. Thus, while it is scanning the heap, the reachability graph is changed by the user program concurrently. If the collector uses this naive search, it may miss some live items. If, for example, (see FIG. 1) the user program moves a white node (1) from being reference by a gray object (2) (i.e., whose children (3 and 4) have not yet been traced) to being referenced by a black object (5) (whose sons (6, 7) will not be traced any more), then the white object (1) (and its sons, if any) may not be traced.
To solve this problem and let the collector spot all live objects during the trace, the program threads help the collector through a write barrier. During the time that the collector performs the tracing of the heap, whenever a pointer is modified from pointing to an object A into pointing to object B, either A or B are marked gray by the modifier thread (by the embodiment of FIG. 1 object (1) is marked gray either when the connection to (5) is created or when reference from (2) is erased). Choosing which of the objects to mark is up to the specific algorithm. In some algorithms both A and B may be marked gray. This operation of the program is sometimes called the "write barrier" or the "update protocol".
Another issue is how to color newly allocated objects during the collection. A solution to the latter problem is sometimes called the "create protocol".
The specific details of an on-the-fly algorithm are well documented in the literature and therefore will not be expounded upon herein.
Turning now to generational garbage collection, the idea was introduced by Lieberman and Hewitt [13]. Generational garbage collectors rely on the assumption that many objects die young. The heap is partitioned into two parts: the young generation and the old generation. New objects are allocated in the young generation which is collected frequently. (See FIG. 2)
Young objects that survive several collections are "promoted" to the older generation. Since the young generation is kept small, most collections are fast and do not stall the application for too long, giving rise to the following advantages:
1. Most collections are fast and efficient: they concentrate on the young part where a high percentage of garbage is normally found. PA1 2. The young generation is frequently collected and therefore can be frequently reused. PA1 3. The collector uses a smaller working set since most collections only scan a small part of the young generation. PA1 4. The specified advantages give rise to an overall system behavior with less paging: the collector traces through less pages and the program keeps a small working set since the heap is reused. PA1 (a) partitioning said heap or portion thereof into at least two generations; and PA1 (b) applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one program thread. PA1 at least one program thread running in said computer system; PA1 a garbage collector for applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one of said program threads.
Traditionally, generational collections partition the heap into the generations in a physical sense. Namely, to promote an object from the young generation to the old generation, the object has to be moved from the young part of the heap to the old part of the heap. Reverting for a moment to on-the-fly collectors it is not recommended to move objects in the heap (by the collector) concurrently with the run of the program since a given object may be used by the program whilst being removed by the collector bringing about obvious undesired results. Whilst the moving object conflict may be resolved by utilizing known per se synchronization primitives, the latter pose an undue overhead on the overall performance of the program/collector.
There follows a brief description of a known per se generational collector that does not move the objects in the heap.
As will be explained below, the latter concept is used by the system and method of the invention. It should be noted, however, that the invention is by no means bound by this particular example.
Thus, Demers et. al. [3] presented a generational collector that does not move the objects in the heap (hereinafter mark and sweep). Their motivation was to allow generational collection when a conservative collection is required.
There follows a brief review of the specified non-moving generational collection technique. The description is focused in a version of the algorithm which is defined in the paper as "the sticky bits". At first the algorithm is described and then the issue of why it constitutes a generational collector is addressed. The description focuses on a "stop the world" collector, i.e., it is assumed that when the collector is run, the program threads (mutators) are stopped. (Of course, in the system and method of the invention the latter stipulation does not apply). It should be noted that the description bellow does not follow Demers exactly. Thus, terminology and concepts that are not mentioned in Demers and yet are useful for understanding the underlying concept of the invention, e.g. "colors" is used.
For a better understanding of the foregoing attention is now directed to FIG. 2 showing a generalized schematic illustration of a heap partitioned to generations. It is assume that, at first stage, memory object (29) and pointer (26) (marked in dashed lines) do not exist and accordingly the heap consists of only objects (23, 24, 27 and 28) Thus, in a mark and sweep algorithm, the collector starts with all allocated objects being white,((23),(24),(27) and (28)), and during the "mark" stage, it marks in black all objects that are reachable from the roots by a path of pointers. (In FIG. 2: (23), (24) and (27)).
First, all objects that are referenced by the stack and registers (the roots) are grayed. Then, all live objects are traced in the following way:
if there is a gray object A, then A gets black color, and for any white object B referenced by A, B gets gray color. The latter series of steps constitute a first form of tracing which continues until there are no more gray objects. All live objects are then black and garbage objects are white. In the embodiment of FIG. 2, only object (28) is white upon completion of the algorithm
After the mark phase is completed and all live objects are colored black, the sweep phase reclaims white objects and re-colors black objects white in preparation for the next garbage collection cycle. This collection which starts with all objects white, marks all live objects, and reclaims all unmarked objects, is called full collection, since all the heap is collected.
In the method of [3], a so-called partial collection is also allowed. Thus, at the end of each collection (while sweeping), black objects are left black and accordingly at the start of the next partial collection many of the live objects in the heap are black. (This is the reason for the name of the method: the bits that mark the object black stick to it, that is, they are not cleared at sweep time.) By the particular example of FIG. 2, objects (23), (24) and (27) remain black.
During the normal operation time, the program threads (also called mutators), record all pointer modifications. To do that, the heap is partitioned into cards, and each card has an associated dirty-bit indicating whether this card was modified since the last collection. A detailed discussion of the known per se card marking can be found in [10]. When a mutator modifies a pointer, (e.g. pointer (26) is added from object (27) to a new object, (29), it marks the card to which the pointer belongs as "dirty" (recording updates is not needed for a full collection).
Thus, all pointers (by this example (26)) that were modified between the collection are on dirty cards. Alternatively, it is possible to keep a dirty bit per object and mark each object as being dirty or not, i.e. mark object (24) as dirty.
A partial collection operates, typically, as follows:
Marking starts with the regular roots marking plus a marking of all white objects referenced from black objects on dirty cards.
In the case that a dirty bit is kept for each object, then all the objects that are referenced by dirty black objects are marked gray. By the specific example of FIG. 2, the marking starts from the root and from the black object (24), which has its dirty bit set. All dirty bits are then cleared.
After this initial marking, a standard tracing is executed: for each object marked gray in the manner specified, mark it black and all its' white descendants gray. This implies that the tracing does not go through black (marked) objects. Namely, when a black object with its dirty bit reset is encountered, its descendants are not traced.
By the embodiment of FIG. 2, if objects (23) and (27) had descendants, the latter would not have been traced since their respective dirty bits are reset. In contrast, object (24) is traced (due to the fact that its dirty bit is set), and therefore, its son (29) is traced and subject to color change (from white through gray to black) in the manner specified.
After tracing, the heap is swept, i.e., all white objects are reclaimed. The marked objects are either unmarked for a next full collection, or remain marked for another partial collection.
Accordingly, it should be noted that in partial collection, despite the fact that black objects are not traced, the dirty bit assumes that "black objects" will be nevertheless, traced, and their descendant duly treated, i.e. assigned with the appropriate color. The net effect is that despite the partial collection, no living object is mistakenly reclaimed.
There follows now brief description for clarifying why the specified algorithm constitutes a generational collector.
In order to explain that, one should think of the black objects as being in the old generation and the white objects as being in the young generation. The part of the heap that is touched during the mark stage contains exactly the objects in the young generation plus the objects in the old generation required to mark inter-generational pointers.
The young generation here contains all objects that were created after the last collection.
Note that all objects that survived the last collection must be black. Thus, the objects in the old generation are not traced.
Objects that are candidates for holding inter-generational pointers are traced. Similar to "regular" generational collection, all modified objects (or all objects on modified cards) must be scanned in order to find all inter-generational pointers (pointing from the old generation to the young generation). Thus, all marked objects on all dirty -cards are scanned and inter-generational pointers are marked: i.e. pointers that point from old objects on dirty cards into the young generation. In the present case, these are dirty black objects. Finally, as always, tracing does not trace through the old generation since black objects are not traversed.
There is accordingly a need in the art to incorporate generations into on-the-fly collector so as to obtain a generational on-the-fly garbage collector which benefits from the advantages (as discussed above) of both conventional generational garbage collector and on-the fly collector.